/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/wood-cut
   @Language: C++
   @Datetime: 16-02-09 08:50
   */

class Solution {
	int count(const vector<int> &L,int len){
		int k=0;
		for(int i=L.size(); i; k+=L[--i]/len);
		return k;
	}

public:
	/**  
	 *@param L: Given n pieces of wood with length L[i]
	 *@param k: An integer
	 *return: The maximum length of the small pieces.
	 */
	int woodCut(vector<int> &L, int k) {
		// write your code here
		if (L.size()==0) return 0;
		int begin=1, end=*max_element(L.begin(),L.end()), mid;
		while(begin<=end){
			mid = begin+(end-begin)/2;
			if (count(L,mid)<k) end=mid-1;
			else begin=mid+1;
		}
		return begin-1;
	}
};
